Digital watermarking is a process for modifying physical or electronic media to embed a hidden machine-readable code into the media. The media may be modified such that the embedded code is imperceptible or nearly imperceptible to the user, yet may be detected through an automated detection process. Most commonly, digital watermarking is applied to media signals such as images, audio signals, and video signals. However, it may also be applied to other types of media objects, including documents (e.g., through line, word or character shifting), software, multi-dimensional graphics models, and surface textures of objects.
Digital watermarking systems typically have two primary components: an encoder that embeds the watermark in a host media signal, and a decoder that detects and reads the embedded watermark from a signal suspected of containing a watermark (a suspect signal). The encoder embeds a watermark by subtly altering the host media signal. The reading component analyzes a suspect signal to detect whether a watermark is present. In applications where the watermark encodes information, the reader extracts this information from the detected watermark.
Several particular watermarking techniques have been developed. The reader is presumed to be familiar with the literature in this field. Particular techniques for embedding and detecting imperceptible watermarks in media signals are detailed in the assignee's application Ser. No. 09/503,881 (now U.S. Pat. Nos. 6,614,914) and 6,122,403, which are hereby incorporated by reference. This application is also related to U.S. Provisional Application 60/404,038, filed Aug. 15, 2002, and 60/428,485, filed Nov. 21, 2002.
The invention provides a method of determining distortion of a signal with embedded data. This method transforms the signal into a transform domain to produce peaks due to a repetitive structure of the embedded data in the signal. The method then performs a re-mapping of the transformed signal to convert distortion into spatial shifts. The method performs a correlation of the mapped signal with a signal representing an expected pattern of peaks associated with the repetitive structure of the embedded data signal. This correlation detects the spatial shifts of the embedded data, and these spatial shifts provide a measure of the distortion of the signal.
This method is specifically used for synchronizing a digital watermark. An embodiment of the method computes an autocorrelation of a watermarked image, maps the autocorrelation signal to a log polar coordinate system, and correlates the log polar representation of the autocorrelation signal with a template to compute rotation and spatial scaling of the embedded digital watermark. In this method, the digital watermark has a regular, repetitive (e.g., periodic) structure. In particular, the watermark w(x,y) is constructed by repeating an elementary watermark tile ŵ(x,y) (of size N×M) in a non-overlapping fashion. This tiled structure of the watermark can be detected by autocorrelation, where the autocorrelation of the watermarked signal has a peak at the center of each tile. These peaks form a template comprising a two dimensional array of uniformly spaced points. Rotation of the watermarked signal causes a rotation of this array. Also, spatial scaling of the watermarked signal changes the spacing between the points. To determine rotation and scale of a geometrically distorted version of the watermarked signal, the watermark detector performs a log-polar transformation of the autocorrelation signal to convert rotation and scale changes to the peaks in the autocorrelation signal to linear shifts. A linear correlation between a template and the autocorrelation peaks in the log polar domain produces a correlation peak at a location corresponding to the rotation and scale of the watermark relative to its original orientation. This rotation and scale is then used to return the watermarked signal to its original orientation. The watermark signal may then be decoded using one of many known watermark encoding/decoding schemes.